#include <iostream>

using namespace::std;

void print_array(int *a, int n)
{
    for(int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}

void shell_sort(int *a, int n)
{
    int inc = n/2;
    int j = 0;
    int i = 0;
    int tmp = 0;
    while(inc > 0)
    {
        for(i = inc; i < n; i += inc) //why i+= inc
        {
            j = i - inc;
            tmp = a[i];
            print_array(a, n);
            while(j >= 0 && a[j] > tmp) //只跟a[i]进行比较
            {
                a[j+inc] = a[j];
                j -= inc;
            }
            a[j + inc] = tmp;
        }
        inc /= 2;
    }
}

int main(int argc, char** argv)
{
    int array[10] = {3, 4, 6, 3, 8, -4, 14, 40, 9, 10};
    int size = sizeof(array)/sizeof(array[0]);
    print_array(array, size);
    shell_sort(array, size);
    print_array(array, size);
}
